package com.yin.algorithms;

import com.yin.Sort;
import com.yin.Util;

public class HeapSort implements Sort {

    //本算法使用大顶堆
    /*
    *   基本概念:
    *   1.  下标为node的父节点下标: (node - 1) / 2（向下取整）
    *   2.  下标为node的左子节点下标: node * 2 + 1
    *   3.  下标为node的右子节点下标: node * 2 + 2
    * */

    @Override
    public void sort(int[] arr) {

        int N = arr.length;

        //从大顶堆的最后一个元素的父节点作为根节点开始建堆
        /*
        *   ((N - 1) - 1) >> 1 -> 从大顶堆的最后一个元素的父节点作为根节点开始建堆
        *   index = (N - 1) -> 堆内最后一个节点在数组中的下标  (index - 1) / 2 -> 最后一个元素的父节点在数组中的下标
        *
        *
        * */
        for(int i = ((N - 1) - 1) >> 1; i >= 0; i--)
            heapify(arr, N, i);

        //排序
        /*
        *   j可以代表堆内最后一个元素的下标
        *   j = arr.length - 1 -> 从最后一个元素开始
        *   j > 0而非j >= 0 -> 堆内只剩一个元素时，该元素有序
        *   由于大顶堆的性质，每次堆顶(arr[0])的元素值必然是堆内最大的值
        *   每次维护完堆都会产生一个堆内最大值，把他换到数组最后的位置，即完成了升序的排序
        * */
        for(int j = arr.length - 1; j > 0; j--) {

            Util.swap(arr, 0, j);
            heapify(arr, j, 0);
        }
    }

    //维护堆的性质
    private void heapify(int[] arr, int n, int node) {

        //拟定最大数下标为当前节点
        int largest = node;

        //左子节点
        int leftChildNode = node * 2 + 1;

        //右子节点
        int rightChildNode = node * 2 + 2;

        //找出arr[node], arr[leftChildNode], arr[rightChildNode]中的最大值放到父节点上并向下递归维护子堆性质不变
        //之所以要小于arr.length是因为，堆存在数组内，超过arr.length之后已经没有节点了

        //左子节点是否存在且大于当前父节点
        if(leftChildNode < n && arr[largest] < arr[leftChildNode]) largest = leftChildNode;

        //右子节点是否存在且大于当前父节点
        if(rightChildNode < n && arr[largest] < arr[rightChildNode]) largest = rightChildNode;

        //如果找出来的最大值不是node节点本身则交换
        //如果交换了则继续向下递归维护子堆的性质
        if(largest != node) {

            Util.swap(arr, largest, node);
            heapify(arr, n, largest);
        }
    }
}
